package main

import "fmt"

/**
Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.

给定一个有序数组，删除重复的元素，并且返回新的长度 注意 不能借助额外的数组

*/

/*
*
方法 快慢指针
快指针i每个循环+1，遍历整个数组
慢指针j标记不重复的字符的索引值，当A[j]!=A[i]时，令A[i+1]=A[i],然后j+1

其实就是拿不重复的最后一个数和未知的数作比较，发现新的不重复的数，就拿过来作为新的最后一个不重复的数，然后不重复的数个数+1

比如1 2 2 3
不重复的数1和当前未知数1判断，相等，下一个循环
不重复的数1和当前未知数2判断，不相等，将下一个位置的不重复的数置为2，不重复数计数索引+1为1，下一循环
不重复的数2和当前未知数2判断，相等，下一循环
不重复的数2和当前未知数3判断，不相等，将下一个位置的不重复的数置为3，不重复数计数索引+1为2，循环结束
故，最后结果是2+1=3个不重复数
https://leetcode.com/problems/remove-duplicates-from-sorted-array/solution/
时间复杂度是O(N)
*/
func removeDuplicates(nums []int) int {
	length := len(nums)
	j := 0
	for i := 0; i < length; i++ {
		if nums[i] != nums[j] {
			j++               // 不重复的数+1
			nums[j] = nums[i] // 用下一位表示新的不重复的数
		}
	}

	return j + 1
}

func main() {
	s := []int{1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5}
	length := removeDuplicates(s)
	fmt.Print(length)
}
